package prefixsum;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 * 暴力法： 可以枚举左右边界 如果中间的求和等于k  计数加一
 */
public class 和为K的子数组_560 {

    /**
     * 暴力法
     * O(n^2)  O(1)
     */
    public int subarraySum_force(int[] nums, int k) {
        int len = nums.length;
        int cnt = 0;
        for(int start = 0; start < len; start ++) {
            int sum = 0;
            for(int end = len - 1; end > start; end --) {
                sum += nums[end];
                if(sum == k) cnt ++;
            }
        }
        return cnt;
    }

    /**
     * 利用前缀和加速求和的过程
     */
    public static int subarraySum_prefixsum(int[] nums, int k) {
        int len = nums.length;
        int[] prefixsum = new int[len+1];
        prefixsum[0] = 0; // 第一个设置为0  如 1，1，1  k = 2  prefixsum = 0，1，2，3  能用2 - 0 求前两位的和
        for (int i = 1; i < len + 1 ; i++) {
            prefixsum[i] = prefixsum[i-1] + nums[i - 1];
        }
        int cnt = 0;
        for(int start = 0; start < len + 1; start ++) {
            for(int end = len ; end > start; end --) {
                if(prefixsum[end] - prefixsum[start] == k) cnt ++;
            }
        }
        return cnt;
    }

    /**
     * 利用前缀和  及 hashmap   加速求和的过程
     *
     * 找历史presumPre 中   前缀和为   当前 presumNow -k 的个数  若有  说明   presumNow -presumPre = k  从 pre位置 到 now 位置中间和为k
     */
    public int subarraySum_prefixsum_with_hash(int[] nums, int k) {
        int len = nums.length;
        // int[] prefixsum = new int[len+1];
        // prefixsum[0] = 0; // 第一个设置为0  如 1，1，1  k = 2  prefixsum = 0，1，2，3  能用2 - 0 求前两位的和

        Map<Integer, Integer> cntMap = new HashMap<>();
        cntMap.put(0, 1); // 设置一个0  保证最前面几个元素求和能查到
        int cnt = 0, prefixsum = 0;
        for (int i = 0; i < len  ; i++) {
            prefixsum += nums[i];
            if(cntMap.containsKey(prefixsum - k)) {
                cnt += cntMap.get(prefixsum - k);
            }
            cntMap.put(prefixsum, cntMap.getOrDefault(prefixsum, 0) + 1);
        }
        return cnt;
    }

    public static void main(String[] args) {
        subarraySum_prefixsum(new int[]{1,1,1}, 2);
    }
}
